1. Field of the Invention
This invention relates to computer systems, and more particularly, to methods and apparatus for describing computer output images.
2. History of the Prior Art
In three dimensional graphics, surfaces are typically rendered by assembling a plurality of polygons in a desired shape. The polygons are conventionally triangles because the three vertices of a triangle define a plane in world space which is convenient to describe mathematically. Other polygons restricted to plane surfaces may be similarly described. Such polygons are typically delineated by vertices which are defined by three dimensional coordinates in world space, by color values, by texture coordinates, and the like. The color values define the brightness of each of red/green/blue (r, g, b) colors at each vertex and thus the color at each vertex. The texture coordinates (u, v) define the coordinates of each vertex on a texture map defined by values stored in memory. Such a texture map describes a pattern to be applied to the surface of the triangle to vary the color in accordance with the pattern. The texture coordinates of the vertices of a triangular surface area define the position of the triangle on, and thus addressed into, the texture map. Other characteristics such as transparency, specular color values, and additional textures also define each vertex to provide more sophisticated rendering. In this specification, each of these different values at vertices of the triangle is referred to as an attribute.
Generally, surfaces represented by an assembly of polygons are being viewed in perspective so that the values of most of the attributes provided by an application program are values in world space. However, the three dimensional world space coordinates of the vertices are usually furnished by an application program already transformed into screen coordinates in which horizontal and vertical values (x, y) define screen position and a depth value z determines how near a vertex is to the screen and thus whether that vertex is viewed with respect to other points at the same screen coordinates.
In order to provide the data to be stored in a frame buffer by which a triangle may be drawn on the two dimensional screen, the coordinates furnished by an application program for each vertex must be used to determine screen coordinates of all of the pixels across the entire surface of the polygon at which the various attributes will be determined. Once the pixel positions are determined, the other attributes must be assigned at each pixel position.
If the x and y coordinates are furnished in screen values, then the triangle is positioned in screen space so that all of the pixels defining that triangle are determined. If the x and y coordinates are instead furnished in world coordinates, then the screen vertices of the particular triangle are first determined from the world three dimensional coordinates so that all of the pixels defining that triangle may be determined. This is typically accomplished by a simple conversion process well known to those skilled in the art.
The pixels which describe a particular triangle are typically determined by a series of linear interpolations using the x and y screen coordinates. This process essentially requires dividing the change in the x or the y coordinates between two vertices by the number of pixels between the vertex to determine a per pixel change and incrementing the coordinate by the result for each sequence of coordinates from one vertex to the next. If the edge pixels of the triangle are known, then the coordinates of the pixels on each scan line may be obtained by the interpolation process across from edge to edge across each scan line.
At each pixel position determined, a similar process is typically used by the prior art to determine the value of each of the attributes at the pixel position. However, while the pixel determination is accomplished by linear interpolation in screen space, since the original triangle lies in a plane in world space, the values of each of the attributes varies linearly in world space from one to another of the vertices of the triangle. In order for the attribute values to be reasonably correct at any pixel position on the screen, each of the attributes must be evaluated by linear interpolation in world space and then related back to the pixel position in screen space by a perspective correction process in which the values of the attributes are determined at each screen pixel.
In order to evaluate the values of the many attributes in world space and relate those values back to screen space, a very large amount of computing power is required. Heretofore, the number of steps required to accomplish the computations and the amount of circuitry required have been just too great to allow correct results to be produced. For example, the number of steps required to compute linear values in world space for each of the large number of different attributes is significant. Then, to go through the process of relating each of the values back to screen space through a perspective correction manipulation overwhelms the ability of most computers. Consequently, most prior art graphics circuits merely perform a linear interpolation process in screen on the world space attribute values for each pixel as though the values were screen space values. In many cases, the results produced are not noticeably incorrect. For example, it is difficult to tell what r, g, b color should be at a particular pixel without knowing what the result should look like. Similarly, the fog values which should occur at a particular pixel are difficult to evaluate.
Certain of the attributes produce bizarre results when handled in this manner, however. For example, the application of textures to surfaces is often obviously incorrect even to the untrained eye. For this reason, some prior art graphics processes do evaluate texture coordinates in world space and carry out perspective correction to provide texture coordinates in screen space as each pixel position is computed. However, these processes tend to be quite slow. As to the other attributes, the typical solution is to either ignore the problem or to apply some form of estimated correction to the values as they are generated. In any case, no known graphics circuitry has produce perspective-correct results for all attributes utilized in the process.
Another problem which is encountered in providing perspective correct results using prior art graphics accelerator circuitry derives from the linear interpolation processes used to determine pixel position and attribute values. When a linear interpolation process is used to determine edge coordinates for pixels, the values of those coordinates are not necessarily integrals. Some compromise process such as rounding or truncating is typically used in order to obtain integral values so that actual pixels may be evaluated. However, these processes have all been compromises and the actual values are not provided. Consequently, any scan line of pixels may be off by as much as one full pixel from end to end. When these values are used to determine values for the various attributes, the attribute values similarly lack precision. Moreover, although the values provided for each of the attributes at each vertex are often quite precise, these values are usually not integral values. Consequently, each linear interpolation process used to determine an attribute value produces similar compromises. Consequently, none of the prior art graphics processes produces correct results.
It is desirable to provide apparatus and an improved method for carrying out more rapidly the process of determining the perspective correct screen values of each of the attributes of each pixel defining a polygon.